package 题目集.动态规划.枚举行为优化;

import org.junit.Test;

/**
 * https://leetcode.cn/problems/best-time-to-buy-and-sell-stock-iii 给定一个数组，它的第 i
 * 个元素是一支给定的股票在第 i 天的价格。 设计一个算法来计算你所能获取的最大利润。你最多可以完成 两笔 交易。
 */
public class ch01_股票问题3 {
	/**
	 * 记录每个位置，最多只交易一次能获得的最大价值
	 * 枚举每个数作为第二个位置，左侧所有数作为第二个买入位置能取到的最大值
	 * @param prices
	 * @return
	 */
	public int maxProfit(int[] prices) {
		int[] dp1 = new int[prices.length];
		int[] dp2 = new int[prices.length];
		int ans = 0;
		int min = prices[0];
		for (int i = 1; i < prices.length; i++) {
			min = Math.min(min, prices[i]);
			dp1[i] =Math.max(dp1[i-1], prices[i] - min);
			for(int j=0;j<i;j++) {
				dp2[i]=Math.max(dp2[i], dp1[j]+prices[i]-prices[j]);
			}
			ans = Math.max(ans, dp2[i]);
		}
		return ans;
	}
	/**
	 * 观察枚举行为，得出的优化。
	 * 发现dp2[i]依赖与左侧所有位置中，dp1[j]-prices[j]最大的一个
	 * 优化1：我们可以开一个数组，专门记录每个位置左侧dp1[j]-prices[j]的最大值
	 * @param prices
	 * @return
	 */
	public int maxProfit2(int[] prices) {
		int[] dp1 = new int[prices.length];
		int[] dp2 = new int[prices.length];
		int depence=Integer.MIN_VALUE;	//专门记录当前位置左侧dp1[j]-prices[j]的最大值
		int ans = 0;
		int min = prices[0];
		for (int i = 1; i < prices.length; i++) {
			min = Math.min(min, prices[i]);
			dp1[i] =Math.max(dp1[i-1], prices[i] - min);
			depence=Math.max(depence, dp1[i]-prices[i]);
			dp2[i]=prices[i]+depence;
			ans = Math.max(ans, dp2[i]);
		}
		return ans;
	}
	/**
	 * 2中引入了一个depence[i]信息，但这个信息在dp1中已经包含了
	 * @param prices
	 * @return
	 */
	public int maxProfit3(int[] prices) {
		int[] dp1 = new int[prices.length];
		int[] dp2 = new int[prices.length];
		int ans = 0;
		int min = prices[0];
		for (int i = 1; i < prices.length; i++) {
			min = Math.min(min, prices[i]);
			dp1[i] =Math.max(dp1[i-1], prices[i] - min);
			dp2[i]=Math.max(dp2[i-1]-prices[i-1]+prices[i],  dp1[i-1]+prices[i]-prices[i-1]);
			ans = Math.max(ans, dp2[i]);
		}
		return ans;
	}
	@Test
	public void test() {
		int[] prices = { 3, 5, 0, 4 };
		int res = maxProfit(prices);
		System.out.println(res);
	}

}
